package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/swap-nodes-in-pairs/"> 两两交换链表中的节点(Swap Nodes in Pairs)</a>
 * <p>给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *          1 -> 2 -> 3 -> 4
 *      ==> 2 -> 1 -> 4 -> 3
 *      输入：head = [1,2,3,4]
 *      输出：[2,1,4,3]
 *
 * 示例 2：
 *      输入：head = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：head = [1]
 *      输出：[1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中节点的数目在范围 [0, 100] 内</li>
 *     <li>0 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @since 2023/4/27 9:18
 */
public class LC0024SwapNodesInPairs_M {
    static class Solution {
        public ListNode swapPairs(ListNode head) {
            //return swapPairsByIterator(head);
            return swapPairsByRecursion(head);
        }

        private ListNode swapPairsByIterator(ListNode head) {
            // 用一个虚拟节点记录，用于返回头节点
            ListNode dummyNode = new ListNode(-1, head);
            ListNode currNode = dummyNode;
            while (currNode.next != null && currNode.next.next != null) {
                ListNode next1Node = currNode.next;
                ListNode next2tNode = currNode.next.next;
                ListNode next3Node = currNode.next.next.next;
                currNode.next = next2tNode;
                next2tNode.next = next1Node;
                next1Node.next = next3Node;
                currNode = currNode.next.next;
            }
            return dummyNode.next;
        }

        private ListNode swapPairsByRecursion(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode listNode = swapPairsByRecursion(head.next.next);
            ListNode nextNode = head.next;
            nextNode.next = head;
            head.next = listNode;
            return nextNode;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        Solution solution = new Solution();
        Printer.printListNode(solution.swapPairs(head));
    }
}
